The present invention relates to digital cellular telephone systems and more particularly to decoders employed in such systems and other applications to decode messages convolutionally encoded by a technique called tail biting encoding.
Traditional cellular telephone systems have generally been based on the use of analog hardware for channel communication. In the analog system design, a single mobile phone is assigned to each assigned frequency in each cell.
More recently, digital cellular telephone systems have been and are being developed for commercial application. In the digital cellular system design, additional phone capacity is achieved by allocating multiple subscribers to each assigned frequency with the use of time-multiplexing techniques.
In implementing digital technology in the design of cellular telephone systems, competitive pressures make it especially immportant that design complexity be avoided or reduced with cost effectiveness while achieving quality product performance in accordance with applicable performance standards. Decoding of encoded messages is one product area where a need has existed for application of this design philosophy to achieve better and less expensive cellular mobile units and base stations.
In the North American Digital Cellular System, control messages are occasionally transmitted between the base station and a mobile unit. The control messages are called FACCH (Fast Associated Control CHannel) message and are convolutionally encoded for error protection, with use of a technique called tail-biting encoding. A FACCH word has a length L=65, the encoding rate is 1/4, and 260 bits are accordingly output for each word. A tail-biting code differs from a zero tail code in that in the zero-tail code the first and last states are known, while, in a tail-biting code, the first and last states are the same, but they are unknown to the decoder.
Although there is ample literature on decoding convolutional codes, there is little literature on decoding tail biting codes. In one prior art scheme for decoding tail biting codes, three decoding methods are employed. In each of these methods, a Viterbi decoder is run several times, with a different starting state each time, until a final state is found that matches the starting state. The difference among these methods is in the choice of the starting state that will decrease the number of runs. The number of runs is still very high in each case and, as a result, these prior art methods are not practically implementable in real time software on a digital signal processor in a digital cellular unit. In another prior art decoding procedure for tail biting codes, numerous required runs also employ excessive CPU execution time.
Prior art decoders for tail biting codes have typically required special hardware circuitry for implementation of the complex decoding process, resulting in higher product costs as well as delay in product availability for the market. In general, such decoders have not been adaptable to lower cost software implementation and have been impractical for commercial application in cellular telephone and other systems.
The present invention is directed to providing improved and less costly decoding of messages, and especially control messages that are received in a cellular base or mobile unit in a digital cellular system.